package com.dh.leetcode.two;

import org.junit.Assert;
import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @ClassName: _299_bulls_and_cows
 * @Description: 299. 猜数字游戏
 * @Author: shouzimu 你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：
 * <p>
 * 写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：
 * <p>
 * 猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls", 公牛），
 * 有多少位属于数字猜对了但是位置不对（称为 "Cows", 奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。
 * 给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。
 * <p>
 * 提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。
 * <p>
 * 请注意秘密数字和朋友猜测的数字都可能含有重复数字。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: secret = "1807", guess = "7810"
 * 输出: "1A3B"
 * 解释: 数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
 * "1807"
 * |
 * "7810"
 * 示例 2:
 * <p>
 * 输入: secret = "1123", guess = "0111"
 * 输出: "1A1B"
 * 解释: 数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
 * "1123"        "1123"
 * |      or     |
 * "0111"        "0111"
 * 注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。
 * 示例 3：
 * <p>
 * 输入：secret = "1", guess = "0"
 * 输出："0A0B"
 * 示例 4：
 * <p>
 * 输入：secret = "1", guess = "1"
 * 输出："1A0B"
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/bulls-and-cows
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * 提示：
 * <p>
 * 1 <= secret.length, guess.length <= 1000
 * secret.length == guess.length
 * secret 和 guess 仅由数字组成
 *
 * @Author: shouzimu
 * @Date: 2021/11/8 11:30
 */
public class _299_bulls_and_cows {


    /**
     * 第一版，使用Map+set记录各个数字出现的位置
     * 例如其中一个数字的set
     * 0 -  1 2 3
     * 0 -  1 3
     * <p>
     * set较短的长度为母牛初始长度
     * 遍历set，遇到相同的则公牛+1  母牛-1
     * 对于上面的情况  公牛2  母牛0
     *
     * @param secret
     * @param guess
     * @return
     */
    public String getHintV1(String secret, String guess) {
        int a = 0, b = 0;
        Map<Character, Set> secretMap = new HashMap<>();
        Map<Character, Set> guessMap = new HashMap<>();
        char[] sa = secret.toCharArray();

        for (int j = 0; j < sa.length; j++) {
            Set<Integer> set = secretMap.getOrDefault(sa[j], new HashSet());
            set.add(j);
            secretMap.put(sa[j], set);
        }

        char[] ga = guess.toCharArray();
        for (int j = 0; j < ga.length; j++) {
            Set<Integer> set = guessMap.getOrDefault(ga[j], new HashSet());
            set.add(j);
            guessMap.put(ga[j], set);
        }

        for (Map.Entry<Character, Set> integerSetEntry : guessMap.entrySet()) {
            char key = integerSetEntry.getKey();
            Set<Integer> value = integerSetEntry.getValue();
            Set<Integer> secretSet = secretMap.get(key);
            if (null != secretSet) {
                int btmp = Math.min(value.size(), secretSet.size());
                for (Integer integer : value) {
                    if (secretSet.contains(integer)) {
                        a++;
                        btmp--;
                    }
                }
                b += btmp;
            }
        }
        return a + "A" + b + "B";
    }

    /**
     * v1实现的进一步简化
     *
     * 使用桶记录下每个数字出现的位置不同次数，较小的一个就是母牛长度
     *
     * @param secret
     * @param guess
     * @return
     */
    public String getHint(String secret, String guess) {
        int a = 0, b = 0;
        int[] sBuckey = new int[10];
        int[] gBuckey = new int[10];
        for (int i = 0; i < guess.length(); i++) {
            int sv = secret.charAt(i) - '0';
            int gv = guess.charAt(i) - '0';
            if (sv == gv) {
                a++;
            } else {
                sBuckey[sv]++;
                gBuckey[gv]++;
            }
        }
        for (int i = 0; i <= 9; i++) {
            b += Math.min(sBuckey[i], gBuckey[i]);
        }
        return a + "A" + b + "B";
    }


    @Test
    public void getHintTest() {
        Assert.assertEquals("1A2B", getHint("1100", "1011"));
        Assert.assertEquals("1A3B", getHint("1807", "7810"));
        Assert.assertEquals("1A1B", getHint("1123", "0111"));
        Assert.assertEquals("0A0B", getHint("1", "0"));
        Assert.assertEquals("1A0B", getHint("1", "1"));
    }

}
